//#include <iostream>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <functional>
//#include <climits>
//#include <cstring>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//vector<int>v;
//vector<int>book;
//
//void dfs(int n)
//{
//	if (v.size() == n)
//	{
//		for (auto e : v)
//			cout << e << ' ';
//		cout << endl;
//		return;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (!book[i])
//		{
//			book[i] = 1;
//			v.push_back(i);
//			dfs(n);
//			v.pop_back();
//			book[i] = 0;
//		}
//	}
//}
//
//int main()
//{
//	int n;
//	cin >> n;
//	book.resize(n + 1, 0);
//	dfs(n);
//	return 0;
//}